//我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
//
//
//
// 示例:
//
// 输入: n = 10
//输出: 12
//解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
//
// 说明:
//
//
// 1 是丑数。
// n 不超过1690。
//
//
// 注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
//
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 468 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function nthUglyNumber(n: number): number {
    //? dp[i]表示第i个丑数
    //? 每一个已知的丑数乘以2 3 5后都会变成丑数
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    //? 指针指向下一个*2 *3 *5的丑数的位置 这三个指针分别计算
    let p2 = 1, p3 = 1, p5 = 1;
    for (let i = 2; i <= n; i++) {
        const num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
        //? 去三个中最小的那个 就是下一个丑数
        dp[i] = Math.min(Math.min(num2, num3), num5);
        //? 更新指针
        if (dp[i] === num2) {
            p2++;
        }
        if (dp[i] === num3) {
            p3++;
        }
        if (dp[i] === num5) {
            p5++;
        }
    }
    return dp[n];
};
//leetcode submit region end(Prohibit modification and deletion)
